Năm 1624, Quốc vương Agung của Mataram đã chinh phục Madura và chính quyền của đảo về tay Cakraningrat, một dòng dõi ông hoàng duy nhất. Gia tộc Cakrangingrat chống đối sự cai trị của Java và thường xuyên xâm chiếm phần lớn Mataram.

Sau chiến tranh Kế vị Java lần I giữa Amangkurat III và bác/chú là Pangeran Puger, người Hà Lan giành được quyền kiểm soát nửa phía đông của vào năm 1705. Người Hà Lan công nhận Puger do ảnh hưởng của lãnh chúa Tây Madura, Cakraningrat II hỗ trợ Puger với hi vọng một cuộc chiến tranh mới ở Trung Java sẽ giúp người Madura có cơ hội để can thiệp. Tuy nhiên, khi Amangkurat II bị bắt và đưa đi lưu đày ở Tích Lan (Sri Lanka ngày nay), Puger đã đạt được tước hiệu Pakubuwono I và ký một thỏa ước với người Hà Lan, theo đó, ban cho họ vùng Đông Madura.

Gia tộc Cakraningrat đã giúp đỡ người Hà Lan dập tắt cuộc nổi loạn năm 1740 Trung Java sau vụ thảm sát người Hoa vào năm 1740. Theo một điều ước năm 1743 với Hà Lan, Pakubuwono I nhượng toàn bộ chủ quyền Madura cho Hà Lan, song bị Cakraningrat IV chống đối. Cakraningrat chạy đến Banjarmasin, trú ẩn cạnh người Anh, và sau đó bị người Hà Lan bắt và lưu đày đến Mũi Hảo Vọng.

Người Hà Lan duy trì bốn đơn vị hành chính tại Madura và mỗi đơn vị có người nhiếp chính riêng. Hòn đảo ban đầu có vai trò quan trọng trong việc cung cấp quân đội thuộc địa và đến nửa cuối thế kỷ XIX, nó đã trở thành nguồn cung muối chính cho các lãnh thổ thuộc địa của Hà Lan tại quần đảo Mã Lai.